/**
 * 3.2数据结构与算法-线性表
 * 编程题
 * 36.请编写一个程序，返回链表中倒数第k个节点。
 */
/**
 * 1.宏定义
 * 2.类型
 * 3.结构体
 * 4.初始化
 * 5.插入
 * 6.返回倒数第k个
 * 7.main
 */
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define Status int

typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode * next;
}LNode,*LinkList;

// 初始化链表
LinkList InitList(){
    LNode* L = (LNode*)malloc(sizeof(LNode));
    if(L==NULL){
        return ERROR;
    }
    L->next = NULL;
    return L;
}
//插入
Status ListInsert(LinkList L, int i, ElemType e){
    //head headnext 
    if(L==NULL){
        return ERROR;
    }
    
    if(i<1){
        return ERROR;
    }
    LNode* p =L;
    int j=0;
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    LNode* newnode = (LNode*)malloc(sizeof(LNode));
    if(newnode==NULL){
        return ERROR;
    }

    newnode->data=e;
    newnode->next=p->next;
    p->next=newnode;

    return OK;
}
// 返回倒数第k个节点,头节点不存算0节点
ElemType PrintfDK(LinkList L,int dk){
    if(L==NULL){
        return ERROR;
    }
    LNode *p =L;
    LNode *q =L;
    for(int i=0;i<dk;i++){//走k步到第k-1个  k- 1 +x    x-1 +k
        p = p->next;
    }
    if(p==NULL){
        return ERROR;
    }
    while(p->next!=NULL){
        p = p->next;
        q = q->next;
    }
    return q->next->data;
}
int main(){
    LinkList L = InitList();

    int n;
    printf("how\n");
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int e;
        scanf("%d",&e);
        ListInsert(L,i,e);
    }
    printf("%d\n",PrintfDK(L,3));
}